package com.github.yangyishe.p100;

import java.util.HashMap;
import java.util.Map;

/**
 * 使用滑动窗口解决问题3
 */
public class Problem03Window {
    public static void main(String[] args) {
        String s="abba";

        Problem03Window problem03Window = new Problem03Window();
        int i = problem03Window.lengthOfLongestSubstring(s);
        System.out.println(i);

    }

    /**
     * 几乎是最佳解决方案了
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s){
        int left=0;
        Map<Character,Integer> char2IndexMap=new HashMap<>();
        int maxLen=0;
        // 变动长度窗口滑动的模板遍历. 将i视为right, 则难点就落在如何快速确定left身上了
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            // 针对本题, 一种更取巧的方式
            if(char2IndexMap.containsKey(c)){
                Integer occurIndex = char2IndexMap.get(c);
                if(occurIndex>=left){
                    left= occurIndex +1;
                }
            }

            // 裁剪元素后的区域, 必为业务可判断区
            maxLen=Math.max(maxLen,i-left+1);

            char2IndexMap.put(c,i);
        }

        return maxLen;
    }

    /**
     * 按照模板来的代码
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring2(String s){
        int left=0;
        int right=0;

        Map<Character,Integer> char2CountMap=new HashMap<>();
        int maxLen=0;
        while(right<s.length()){
            char c = s.charAt(right);
            if(char2CountMap.containsKey(c)){
                char2CountMap.put(c,char2CountMap.get(c)+1);
            }else{
                char2CountMap.put(c,1);
            }

            while(char2CountMap.get(c)>1){
                char2CountMap.put(s.charAt(left),char2CountMap.get(s.charAt(left))-1);
                left++;
            }

            // 处理逻辑
            maxLen=Math.max(maxLen,right-left+1);

            right++;
        }

        return maxLen;
    }
}
